package com.fosss.horse;


import java.awt.*;
import java.util.ArrayList;
import java.util.Comparator;

/**
 * !!!!!!!!注意横纵坐标和行数列数的对应关心！！！！！！！！！！！！！！！！
 */
public class HorseChessBoard {
    //棋盘的列数
    private int m;
    //棋盘的行数
    private int n;
    //棋盘的各个位置是否走过
    private boolean[][] visited;
    //棋盘
    private int[][] chessBoard;
    //表示棋盘的每个位置是否都被访问过
    private boolean finished;

    /**
     * 构造方法
     */
    public HorseChessBoard(int m, int n) {
        this.m= m;
        this.n = n;
        //初始化二维数组
        visited = new boolean[m][n];
        //初始化棋盘
        chessBoard=new int[m][n];
    }

    /**
     * 判断四周哪个位置可以走，将坐标记录在集合中
     * @ !!!!!!!!!!必须按顺时针或逆时针判断!!！！！！！！！
     */
    private ArrayList<Point> canGo(Point point) {
        ArrayList<Point> arrayList = new ArrayList<>();
        Point p = new Point();
        //！！！！！！注意棋盘的左上角为坐标原点,向右向左为正方向

        //判断5位置能不能走
        if (((p.x = point.x - 2) >= 0) && ((p.y = point.y - 1) >= 0)) {
            arrayList.add(new Point(p));//必须重新new一个对象 TODO
        }
        //判断6位置能不能走
        if (((p.x = point.x - 1) >= 0) && ((p.y = point.y - 2) >= 0)) {
            arrayList.add(new Point(p));
        }
        //判断7位置能不能走
        if (((p.x = point.x + 1) < m) && ((p.y = point.y - 2) >= 0)) {
            arrayList.add(new Point(p));
        }
        //判断0位置能不能走
        if (((p.x = point.x + 2) < m) && ((p.y = point.y - 1) >= 0)) {
            arrayList.add(new Point(p));
        }
        //判断1位置能不能走
        if (((p.x = point.x + 2) < m) && ((p.y = point.y + 1) < n)) {
            arrayList.add(new Point(p));
        }
        //判断2位置能不能走
        if (((p.x = point.x + 1) < m) && ((p.y = point.y + 2) < n)) {
            arrayList.add(new Point(p));
        }
        //判断3位置能不能走
        if (((p.x = point.x - 1) >= 0) && ((p.y = point.y + 2) < n)) {
            arrayList.add(new Point(p));
        }

        //判断4位置能不能走
        if (((p.x = point.x - 2) >= 0) && ((p.y = point.y + 1) < n)) {
            arrayList.add(new Point(p));
        }


        return arrayList;
    }

    /**
     * 实现马踏棋盘算法
     * @param row 第几行
     * @param column 第几列
     * @param step 走的步数
     */
    public void horseChessBoardGo(int row,int column,int step){
//        showChessboard();
//        System.out.println();

        //设置当前位置的步数  注意先y再x!!!!!!!!
        chessBoard[row][column]=step;
        //首先将当前位置设置为已访问
        visited[row][column]=true;//注意先y再x!!!!!!!!
        //得到当前位置可以走的方向
        ArrayList<Point> arrayList = canGo(new Point(column,row));//横坐标代表列，纵坐标代表行

        //优化！！！！！！！！！
        sort(arrayList);

        while (arrayList.size()!=0){//arrayList.size()!=0!!!!!!!!!
            //取出可以走的位置
            Point point = arrayList.remove(0);
            //判断该点是否已经走过,没有走过的话就递归继续走,步数加一
            if(!visited[point.y][point.x]){
                horseChessBoardGo(point.y,point.x,step+1);//!!!!!!!!注意横纵坐标和行数列数的对应关心
            }
        }
        /**
         * 判断是否完成了所有该算法
         * //说明: step < X * Y 成立的情况有两种
         * //1. 棋盘到目前位置,仍然没有走完
         * //2. 棋盘处于一个回溯过程
         */
        if(step<m*n&&!finished){
            chessBoard[row][column]=0;//该处步数设置为0
            visited[row][column] = false;//标志成没有访问过

        }else {
            //完成
            finished=true;
        }
    }

    /**
     * 打印最后的棋盘
     */
    public void showChessboard(){
        for (int i = 0; i < chessBoard.length; i++) {
            for (int j = 0; j < chessBoard[i].length; j++) {
                System.out.print(chessBoard[i][j]+" ");
            }
            System.out.println();
        }
    }

    /**
     * 用贪心算法的思想对马踏棋盘算法进行优化
     */
    public void sort(ArrayList<Point> arrayList){
        /*arrayList.sort(new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {
                return canGo(o1).size()-canGo(o2).size();
            }
        });*/
        arrayList.sort((o1,o2)-> canGo(o1).size()-canGo(o2).size()) ;
    }
}


























